This invention is in the field of mass transit systems. Embodiments of this invention are more specifically directed to scheduling and operation of mass transit commuter rail systems.
For many years, citizens of major metropolitan areas throughout the world have relied on commuter rail systems, including surface rail and subways, as an important means of transportation. Because at-grade intersections with motor vehicles are avoided by subway trains, subway systems are especially attractive in densely populated cities. Currently, over two hundred cities in the world operate subway commuter rail systems, serving hundreds of millions of passengers each day.
Commuter rail systems in general, and subway systems in particular, are of course constrained to the physical locations of their tracks and stations. Trains cannot travel except along the rails, and do not stop for loading and unloading except at discrete stations along the railway. The construction cost of the infrastructure components of railways, rails, and stations is a primary determination in the overall size and complexity of a subway system, especially considering the excavation required to build a subway line within (and thus under) an existing city. Because of these constraints, and of the cost required to add lines or additional infrastructure, optimal utilization of the transportation capacity provided by the subway commuter rail system is a highly desirable goal. Underutilization of the subway system is a financial disaster, in that the huge infrastructure costs are not recouped; as such, subway commuter rail construction is often confined to routes that are capable of providing adequate ridership. But these infrastructure costs also inhibit additional capacity from being constructed, if demand for the subway system exceeds its capacity. As a result, many of the world's urban subway systems are overcrowded; indeed, the overcrowded subway systems in Seoul, Korea and Tokyo, Japan often receive worldwide publicity. My U.S. Pat. No. 5,176,082, issued Jan. 5, 1993, describes a passenger loading and unloading control system that provides one way of addressing this overcrowding problem, specifically by scheduling the number of passengers that may board individual train cars at a station according to the number of passengers that are already on those cars; a method of simultaneously loading and unloading passengers, in an orderly manner, is also described in my patent.
The constraint of high infrastructure construction costs is also reflected in passenger travel times. Commuter rail systems present the particular problem that passengers are free to board and exit the subway train at any station along the line. For example, a train that makes n stops along its line will have Σj=2n(j−1) possible individual passenger trips, with the particular trip made by a given passenger defined by the station at which the passenger boards (i.e., the trip origin) and the station at which the passenger chooses to exit the train (i.e., the destination). And, of course, ridership depends on the convenience provided by the subway, which in large part depends on the proximity of subway stations to passenger destinations. The subway system designer and operator is thus faced with a tradeoff between the number of stations along a line and the passenger travel time from origin to terminus. Specifically, while a larger number of stations along a line improves the proximity of the subway to a wide range of destinations, this larger number of stations will necessarily slow the passenger travel time of passengers that do not want to exit the train at a particular station.
One conventional approach to solving the two problems of overcrowded subway train systems and long passenger travel times is the use of express trains, which are trains that do not stop at every station along a line. In some of the larger subway systems, such as those in New York City, Paris, and Seoul, separate railways and station platforms are provided for the express and local trains, enabling the express trains to travel the route without being held up by the slower local trains that stop at each station. In these systems with separate express lines and stations, in which the express trains are not slowed by local trains and stops at local stations, those passengers that board at an express station, remain on an express train throughout their trip, and exit at an express station, have the optimum passenger travel time.
However, many passengers must ride a local train either to travel to an express station, or to travel from the express station to their desired destination, or both. If these passengers wish to take advantage of the express train service, they must make a transfer between the local and express lines at least once during their trip. The total travel time for these passengers thus includes not only the travel time while on the trains, but also the transfer time involved in changing trains at the express stations. One can consider this transfer time to be the sum of several components, including the boarding and deboarding times, the time required for the passenger to walk between the express and local platforms (typically on different subway levels), and also the time spent waiting for the “transfer-to” train to arrive at the station. Typically, the wait time dominates this transfer time, and can be considered as a random variable, with a mean value of about ½ the “headway” time of the “transfer-to” train.
By way of further background, it is known to synchronize the arrival and departure times of express trains at express stations with the arrival and departure times of local trains at those stations, during rush hour periods of the day. For example, the New York City subway system has been known to schedule their express subway service to minimize transfer times between express and local trains, at least during morning rush hour periods. In this way, the wait time that passengers spend waiting for the “transfer-to” train to arrive at the station is reduced.
As evident from this description, however, those subway systems or portions of subway systems that are limited to only a single track in each direction of travel have not been able to provide express service. In such systems, the ultimate speed of travel of an express train, which as such does not stop at local stations located between express stations, will eventually necessarily be limited by the speed of any local train that the express train catches up to along the route.
By way of further background, “side tracks” or “sidings” are used in some railway systems to allow a faster train to pass a stopped or slower train. FIG. 1a illustrates, in plan view, an example of a conventional passenger rail station at which faster trains are allowed to pass slower or stopped trains, using side tracks. In this example, the two-track system includes main line 2WE for trains traveling “west” to “east” in the view of FIG. 1a, and main line 2EW for trains traveling “east” to “west”. Main line 2WE is disposed adjacent to platform 5WE, at which passenger are able to board and de-board west-to-east traveling trains, while main line 2EW is disposed adjacent to platform 5EW, which supports passenger boarding and deboarding for east-to-west travel. This conventional station includes side tracks 4WE, 4EW associated with platforms 5WE, 5EW, respectively. Side tracks 4WE, 4EW can each be coupled to their respective main tracks 2WE, 2EW, such that a train traveling along main track 2WE, for example, can switch over to and travel along side track 4WE at this station, or can instead continue on main track 2WE. As evident from FIG. 1a, in this conventional arrangement, a slower train approaching the station from the west on main track 2WE can switch over to side track 4WE and stop at platform 5WE, allowing a faster train such as an express train to remain on main track 2WE and travel past platform 5WE, effectively passing the slower train that is stopped at platform 5WE on side track 4WE. As such, a two-track subway line including stations such as the conventional station shown in FIG. 1a can support express and local service.
Side track facilities are typically more prevalent at surface rail stations than at subway stations, because the excavation cost etc. involved in adding a side track at a subway station is typically prohibitive. For example, as shown in FIG. 1a, the station must be sufficiently wide (vertical dimension in FIG. 1) to include the two main tracks 2WE, 2EW, two platforms 5WE, 5EW, two side tracks 4WE, 4EW, and the appropriate spacing on either side of each of these structures. If an existing two-track system wished to add express service, the cost of adding side tracks 4WE, 4EW in the manner shown in FIG. 1a is especially prohibitive, and for that reason is seldom carried out. And even in those surface or subway systems in which side tracks are provided at stations, significant wait time is often required for passengers to change from one train to another, as mentioned above.
By way of further background, computer algorithms for optimizing the scheduling of trains are known in the art. U.S. Pat. No. 6,873,962 B1 describes an automated approach for scheduling departure times and velocities of trains traveling along a rail corridor, by deriving and optimizing a cost function that ensures that all intersections (trains meeting or passing one another) occur at locations at which side tracks are in place. U.S. Patent Application Publication No. US 2005/0234757 A1 describes an automated scheduling system for freight trains, in a railway system including side tracks to allow faster trains to pass slower or stopped trains. U.S. Patent Application Publication No. US 2005/0261946 A1 also describes a method and system for calculating a train schedule plan that operates by optimizing a cost function to minimize delays at crossing loops and lateness at key locations along train routes. U.S. Patent Application No. US 2008/0109124 A1 describes a train scheduling method in which placeholders (“virtual consists”) are used to improve the stability of the solution.
However, each of these conventional train scheduling methods and systems apply to the scheduling of trains that are not concerned with allowing passengers to board or de-board at intermediate stations along the route. In other words, these scheduling methods do not involve the problem of passenger transfer from one train to another, nor do they account for trains that allow for the payload to efficiently board and de-board at any particular stop along the route. In other words, these conventional scheduling methods and systems do not solve many of the important and dominant issues involved in commuter rail systems, particularly subway systems.
By way of further background, U.S. Pat. No. 1,604,932 describes a passenger train system in which passenger throughput is increased by providing trains that are longer than the available platforms. Some cars in the train stop at the platform of every station, while other cars in the train stop at the platform only at alternating stations. The cars and platforms are color-coded, so that the passengers are aware of the restrictions.